/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Administrator
 * Date: 2023-05-17
 * Time: 15:37
 */
public class Mysort {

    // 归并排序---递归
    public static void mergeSort(int[] array){
        // write code  here
        if (array == null || array.length < 2) {
            return;
        }
        int[] temp = new int[array.length];
        mergeSort(array, temp, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int[] temp, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(array, temp, start, mid);
        mergeSort(array, temp, mid + 1, end);
        merge(array, temp, start, mid + 1, end);
    }

    private static void merge(int[] array, int[] temp, int start, int mid, int end) {
        int i = start;
        int j = mid;
        int k = start;
        while (i < mid && j <= end) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        while (i < mid) {
            temp[k++] = array[i++];
        }
        while (j <= end) {
            temp[k++] = array[j++];
        }
        for (k = start; k <= end; k++) {
            array[k] = temp[k];
        }
    }



// 归并排序---非递归
    public static void mergeSort1(int[] array){
    // write code here
        int len = array.length;
        int[] result = new int[len];
        int block, start;

        for(block = 1; block < len*2; block *= 2) {
            for(start = 0; start <len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                //两个块的起始下标及结束下标
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                //开始对两个block进行归并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
                }
                while(start1 < end1) {
                    result[low++] = array[start1++];
                }
                while(start2 < end2) {
                    result[low++] = array[start2++];
                }
            }
            int[] temp = array;
            array = result;
            result = temp;
        }
        result = array;
    }


// 计数排序
    public static void countSort(int[] array) {
    // write code  here
        int maxValue = array[0];
        int minValue = array[0];
        for (int i = 0; i < array.length; ++i) {
            if (array[i] > maxValue) {
                maxValue = array[i];
            }

            if (array[i] < minValue) {
                minValue = array[i];
            }
        }

        int range = maxValue - minValue + 1;
        int[] count = new int[range];

        for (int i = 0; i < array.length; ++i) {
            count[array[i] - minValue]++;
        }

        int index = 0;
        for (int i = 0; i < range; ++i) {
            while (count[i] > 0) {
                array[index++] = i + minValue;
                count[i]--;
            }
        }
    }
}
